%amitash do you see this? abracadabra!
%Saturday April 14th, 0900 hrs
%testing
\documentclass[conference]{IEEEtran}
\usepackage{verbatim}
\usepackage{graphicx}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}


\begin{document}

\title{Closeness Centrality}



%\author{
%\IEEEauthorblockN{Amitash Ramesh, Soumya Ramesh, Vinod Sekhar}
%\IEEEauthorblockA{Indian Statistical Institute\\
%Taramani, Chennai - 600113\\
%TN, India\\
%amitashr@gmail.com, soumya666@gmail.com, vinods1991@gmail.com}
%\and
%\IEEEauthorblockN{Sudarshan Iyengar, C. Pandu Rangan}
%\IEEEauthorblockA{Indian Statistical Institute\\
%Taramani, Chennai - 600113\\
%TN, India\\
%sudarshaniisc@gmail.com, prangan55@gmail.com}
%}

\maketitle


\begin{abstract}
Closeness centrality is a measure of the importance of nodes in a network
based on it's distance relative to other nodes. It has widespread importance
in network analysis and navigation in networks. We introduce the concept of
"center-strategicness" to find paths in a network passing through centrally lo-
cated nodes. An application of the same may be in locating a hospital in a city
ensuring that it is situated in a place that is centrally accessible from all major
localities in the city. We know that people are inclined to learn landmarks when
they are asked to navigate from a source to a destination. We note that these
landmarks are nodes that have high closeness-centrality ranking (S. Iyengar et.al
2011) We define a center-strategic path as one in which, the plot of closeness
centralities of the vertices involved in it, has at most one minima. We investi-
gate the presence of center-strategic paths in trees and prove the following-
\\
1: A tree has at most two top ranked closeness centrality vertices.
\\
2: A tree has a center strategic path between any two vertices.


\end{abstract}
\IEEEpeerreviewmaketitle



\section{\label{introduction_section}Introduction}


\section{\textbf{Preliminaries}}

\section{\textbf{Literature}}

\subsection{\textbf{Closeness Centrality}}

\subsection{\textbf{Center Strategicness}}

\section{\textbf{Results and Proofs}}

\subsection*{\textbf{Lemma 1}}

\textit{GIven an undirected tree $T(V,E)$ and if for some $x,y,z \in V$, if $x,y \in E$ and $y,z \in E$ then $V_z^y \subsetneq V_y^x $.}
\\
\subsubsection*{\textbf{Definition 1}}
\textit{Given a graph $G(V,E)$ and vertices $\alpha, \beta, \in V$, by $V_\alpha^\beta$ we mean the set ${v \in V: d(\alpha,v) < d(\beta,v)}$}
\\
Note: By definition, clearly $\alpha \in V_\alpha^\beta$
\\
The following proposition is obvious from the above definition.
\\
\subsubsection*{\textbf{Propostition 1}}

\textit{Given an undirected tree $T(V,E)$ and given any edge $(\alpha, \beta) \in E$, we have $V_\alpha^\beta \cap V_\beta^\alpha = \emptyset$}
\\
\subsubsection*{\textbf{Proof}}
Let $u \in V_z^y \subsetneq V_z^y$. By definition, we know that $d(u,z) < d(u,y)$. We know that, T being a connected undirected tree, there exists a unique path between any two vertices. Consider the path between $u$ and $z$, let us denote this path as $(u, a_1, a_2,..., a_k, z)$. Since $(z,y) \in E$, we have either $a_k = y$ or $y \neq a_i, \forall 1 \leq i \leq k$. We cannot have $a_k = y$, for in that case $y$ will be closer to $u$ than $z$ which would imply that $d(u,z) > d(u,y)$, a contradiction. Which implies that the unique path connecting $u$ and $y$ has to be $(u, a_1, a_2,...,a_k,z,y)$ which is of length $k+2$. Also, since $(x,y) \in E$, the path connecting $u$ to $x$ must be $(u, a_1, a_2,..., a_k, z, y, x)$, of length $k+3$. This implies that $d(u,x) > d(u,y)$. Which in turn implies that $u \in V_y^x$. $\therefore V_z^y \subsetneq V_y^x$. The strict containment is because $y \in V_y^x$ and $y \not\in V_x^y4$. On similar lines, one can prove that $V_x^y \subsetneq V_y^z$.
\\
\subsubsection*{\textbf{Corollary 1}}
\textit{Given an undirected tree $T(V,E)$ and if for some $x,y,z \in V$, if $(x,y) \in E$ and $(y,z) \in E$ then $|V_z^y|<|V_y^x|$ (and $|V_x^y| < |V_y^z|)$.}
\\
\subsubsection*{\textbf{Proof}}
Follows from Lemma 1.
\\
\subsection*{\textbf{Lemma 2}}
\textit{
Given an undirected tree $T(V,E)$, if for some $(x,y) \in E$, if $C(x) \leq C(y)$ then $|V_x^y| \geq |V_y^x|$.}

\subsubsection*{\textbf{Proof}}
We know that: 
        $$C(x) = d(x,V_x^y) + d(x,V_y^x)$$ 
Clearly, $C(x) = d(y, V_x^y) - |V_x^y| + d(y,V_y^x) + |V_y^x|$
\\
$\implies C(x) = C(y) + |V_y^x| - |V_x^y|$
\\
Given that $C(x) \leq C(y)$, we have $|V_x^y| \geq |V_y^x|$.

\subsection*{\textbf{Lemma3}}
\textit{Given an undirected tree $T(V,E)$, if for some $x,y,z \in V, (x,y) \in E, (y,z) \in E$ and if $C(x) \leq C(y)$ then $C(y) < C(z)$.}

\subsubsection{\textbf{Proof}}
$C(z) = d(z,V_z^y) + d(z,V_y^z)$
\\
$C(z) = d(y,V_z^y) - |V_z^y| + d(y, V_y^z) + |V_y^z|$
\\
Also, $C(y) = d(y, V_z^y) + d(y, V_y^z)$
$\therefore C(z) - C(y) = |V_y^z| - |V_z^y| > |V_y^z| - |V_y^x| > |V_x^y| - |V_y^x| > 0$
\\
$\implies C(y) < C(z)$

\subsection{\textbf{Theorem 1}}
\textit{In a tree,the top most ranked closeness centrality vertices are at most two in number.}

\subsubsection*{\textbf{Proof}}
\textit{Let us prove the statement by contradiction. In case there were two non-adjacent vertices $u$ and $v$ such that $C(u) = C(v)$ and $\forall x \in V,x \neq u,x \neq v \Rightarrow C(x) > C(y).$ We know that there is a unique path between $u$ and $v$.Let the path be $(u,\propto_1,\propto_2,...,\propto_k,v)$. Given that $u$ is the top most vertex and that $u$ and $v$ are not adjacent,we have $C(u)<C(\propto_1)$. By Lemma 3.,we have $$ C(\propto_1)<C(\propto_2)<C(\propto_3)<...<C(\propto_k)<C(v)$$,thus arriving at a contradiction.}

\subsection{\textbf{Theorem 2}}
\textit{In a tree,there is always a center-strategic path between any two vertices.}

\subsubsection{\textbf{Proof}}
\textit{Let us first consider the case with top closeness-centrality valued vertex being unique.Consider a tree $T(V,E)$.Let $z$ be the vertex with top closeness centrality.Consider a pair of vertices $u$ and $v$.We know that in a tree,there is a unique path between any two vertices.Let the path between $u$ and $v$ be }

\end{document}


